package 蓝桥杯算法;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class day09 {
    public static void main(String[] args) {
        String a = "asdasdasdasd";
        day09 b = new day09();
        System.out.println(b.repeatedSubString(a));


    }

    public boolean repeatedSubstringPattern(String s) {
        int n = s.length();
        for (int i = 0; i < n / 2; i++) {
            if (n % i != 0) {
                continue;
            }
            boolean isValid = true;
            for (int j = i; j < n; j++) {
                if (s.charAt(j) != s.charAt(j - i)) {//相当于一层一层
                    isValid = false;
                    break;
                }
            }
            if (isValid) {
                return true;
            }
        }
        return false;
    }

    public boolean repeatedSubString(String s) {//移动匹配
        String result = s + s;
        String tirmed = result.substring(1, result.length() - 1);
        return tirmed.contains(s);
    }

    public int removeElement(int[] array, int val) {
        int size = array.length;
        for (int i = 0; i < size; i++) {
            if (array[i] == val) {
                for (int j = i + 1; j < size; j++) {
                    array[j - 1] = array[j];
                }
                size--;
                i--;//在i处的位置变成了新值
            }
        }
        return size;
    }

    public int removeElement1(int[] array, int val) {
        int slow = 0;
        int size = array.length;
        for (int fast = 0; fast < size; fast++) {
            if (array[fast] != val) {
                array[slow] = array[fast];
                slow++;//碰见不同的便会停下来
            }
        }
        return slow;
    }

    public char[] reverse(char[] s) {
        int n = s.length - 1;
        int i = 0;
        while (i < n) {
            char temp = s[i];
            s[i] = s[n];
            s[n] = temp;
            i++;
            n--;
        }
        return s;
    }
    public List<List<Integer>> treeSum(int[] nums){
        List<List<Integer>> result=new ArrayList<>();
        Arrays.sort(nums);
        for(int i=0;i<nums.length;i++){
            if(nums[i]>=0){
                break;
            }
            if(i>0&&nums[i-1]==nums[i]){//去重
                continue;
            }
            int left=i+1;
            int right=nums.length-1;
            while(left<right){
                int sum=nums[i]+nums[left]+nums[right];
                if(sum>0){
                    right--;
                }
                else if(sum<0){
                    left++;
                }
                else{
                    result.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    while(left<right&&nums[right]==nums[right-1]){
                        right--;
                    }
                    while(left<right&&nums[left]==nums[left+1]){//去重
                        left++;
                    }
                    right--;
                    left++;
                }
            }
        }
        return result;
    }
    public List<List<Integer>> fourSum(int[] nums,int target){
        List<List<Integer>> result=new ArrayList<>();
        Arrays.sort(nums);
        for(int i=0;i<nums.length;i++){
            if(nums[i]>=0&&nums[i]>target){
                break;
            }
            if(i>0&&nums[i]==nums[i-1]){//去重
                continue;
            }
            for(int j=i+1;j<nums.length;j++){
                if(nums[i]+nums[j]>target&&nums[i]+nums[j]>=0){
                    break;
                }
                if(j>i+1&&nums[j]==nums[j-1]){
                    continue;
                }
                int left=i+1;
                int right=nums.length-1;
                while(left<right){
                    int sum=nums[i]+nums[j]+nums[left]+nums[right];
                    if(sum>target){
                        right--;
                    }
                    else if(sum<target){
                        left++;
                    }
                    else{
                        result.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                        while(left<right&&nums[left]==nums[left+1]){
                            left++;
                        }
                        while(left<right&&nums[right]==nums[right-1]){
                            right--;
                        }
                        left++;
                        right--;
                    }
                }
            }
        }
        return result;
    }
}

